package org.apache.commons.graph.algorithms.spanning

import org.apache.commons.graph.Graph
import org.apache.commons.graph.GraphException
import org.apache.commons.graph.Mapper
import org.apache.commons.graph.SpanningTree
import org.apache.commons.graph.model.MutableSpanningTree
import org.apache.commons.graph.weight.OrderedMonoid

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 * The predecessor list is a list of vertex of a [org.apache.commons.graph.Graph].
 * Each vertex' entry contains the index of its predecessor in a path through the graph.
 *
 * @param <V> the Graph vertices type
 * @param <E> the Graph edges type
 * @param <W> the weight type
</W></E></V> */
internal class ShortestEdges<V, WE, W>(
    private val graph: Graph<V, WE>,
    private val source: V,
    private val weightOperations: OrderedMonoid<W>,
    private val weightedEdges: Mapper<WE, W>
) : Comparator<V> {

    private val predecessors: MutableMap<V, WE> = HashMap()

    /**
     * Add an edge in the predecessor list associated to the input vertex.
     *
     * @param tail the predecessor vertex
     * @param head the edge that succeeds to the input vertex
     */
    fun addPredecessor(tail: V, head: WE) {
        predecessors[tail] = head
    }

    /**
     * {@inheritDoc}
     */
    override fun compare(left: V, right: V): Int {
        if (!hasWeight(left) && !hasWeight(right)) {
            return 0
        } else if (!hasWeight(left)) {
            return 1
        } else if (!hasWeight(right)) {
            return -1
        }
        return weightOperations.compare(getWeight(left), getWeight(right))
    }

    /**
     * Creates a spanning tree using the current data.
     *
     * @return a spanning tree using current data
     */
    fun createSpanningTree(): SpanningTree<V, WE, W> {
        val spanningTree = MutableSpanningTree<V, WE, W>(weightOperations, weightedEdges)

        for (edge in predecessors.values) {
            val vertices = graph.getVertices(edge)

            val head = vertices!!.head
            val tail = vertices.tail

            org.apache.commons.graph.algorithms.spanning.ShortestEdges.Companion.addEdgeIgnoringExceptions(
                head,
                spanningTree
            )
            org.apache.commons.graph.algorithms.spanning.ShortestEdges.Companion.addEdgeIgnoringExceptions(
                tail,
                spanningTree
            )

            spanningTree.addEdge(head, graph.getEdge(head, tail)!!, tail)
        }

        return spanningTree
    }

    /**
     * Returns the distance related to input vertex, or null if it does not exist.
     *
     * **NOTE**: the method [hasWeight] should be used first to check if
     * the input vertex has an assiged weight.
     *
     * @param vertex the vertex for which the distance has to be retrieved
     * @return the distance related to input vertex, or null if it does not exist
     */
    fun getWeight(vertex: V): W? {
        if (source == vertex) {
            return weightOperations.identity()
        }

        val edge = predecessors[vertex] ?: return null

        return weightedEdges.map(edge)
    }

    /**
     * Checks if there is a weight related to the input `Vertex`.
     *
     * @param vertex the input `Vertex`
     * @return true if there is a weight for the input `Vertex`, false otherwise
     */
    fun hasWeight(vertex: V): Boolean {
        return predecessors.containsKey(vertex)
    }

    val isEmpty: Boolean
        /**
         * Checks the predecessor list has no elements.
         *
         * @return true, if the predecessor list has no elements, false otherwise.
         */
        get() = predecessors.isEmpty()

    /**
     * {@inheritDoc}
     */
    override fun toString(): String {
        return predecessors.toString()
    }

    companion object {
        private fun <V, WE, W> addEdgeIgnoringExceptions(vertex: V, spanningTree: MutableSpanningTree<V, WE, W>) {
            try {
                spanningTree.addVertex(vertex)
            } catch (e: GraphException) {
                // just swallow it
            }
        }
    }
}
